#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

struct store{
    int s, e, l;       
    bool operator< (const store& a){
        return s*(a.l) < l*(a.s);
    }
}stores[N];

int n;
int dp[N];

int main(){
    int T;
    cin >> T;
    int cnt = 1;

    while (T -- ) {
        int m = 0;
        cin >> n;
        for(int i = 1;i <= n;++i) {
            cin >> stores[i].s >> stores[i].e >> stores[i].l;
            m += stores[i].s;
        }
        sort(stores + 1, stores + 1 + n);

        memset(dp, -0x3f, sizeof dp);
        dp[0] = 0;
        //01 背包
        for(int i = 1; i <= n; ++ i )
            for(int j = m; j >= stores[i].s; -- j )
                dp[j] = max(dp[j], dp[j-stores[i].s] + max(0, stores[i].e - (j-stores[i].s) * stores[i].l));

        int ans = 0;
        for(int j = 1; j <= m; ++ j ) ans = max(ans ,dp[j]);

        cout << "Case #" << cnt++ << ":" << " " << ans << endl;
    }
}
